﻿<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
	<head>
		<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
		<title>Recherche A*</title>
		<link rel="stylesheet" type="text/css" href="style.css" />
	</head>
	<body class="twoColFixLtHdr">
    <div id="container">
		<div id="header">Algorithme de recherche de chemin A*</div>

		<div id="menu">
			<ul>
				<li><a href="index.html">Accueil</a></li>
				<li><a href="presentation.html">Présentation</a></li>
				<li><a href="connaissances.html">Connaissances</a></li>
				<li><a href="demarche.html">Démarche</a></li>
				<li><a href="difficultes.html">Difficultés</a></li>
				<li><a href="analyse.html">Analyse</a></li>
				<li><a href="conclusion.html">Conclusion</a></li>
				<li><a href="bibliographie.html">Bibliographie</a></li>
				<li><a href="glossaire.html">Glossaire</a></li>
				<li><a href="telechargement.html">Téléchargement</a></li>
			</ul>
		</div>

		<div id="content"><br />
			<h1><a name="top">Acquisition des connaissances</a></h1><br /><br />
			<h2>A* de base</h2>
			Le A* de base est l’algorithme à sa forme la plus simple. Nous n’avons fait aucune optimisation. Le A* de base est la recherche du chemin le plus optimal dans un monde qui se sépare en case (représenté par des nœuds). Le principe est de trouver le chemin le plus rapide en attribuant des coûts à chaque case et en calculant le chemin qui demande le coût le plus petit. Voici un exemple d’un pseudo code du A*.
			<h3>Pseudo code</h3>
			Ajouter le nœud de départ à la liste ouverte<br />
			Tant que la liste ouverte n’est pas vide<br />
			{<br />
			&nbsp;&nbsp;&nbsp;&nbsp;Nœud <- Nœud ouvert avec le plus petit coût<br />
			&nbsp;&nbsp;&nbsp;&nbsp;Si le nœud est la destination finale<br />
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Ceci est un chemin possible<br />
			&nbsp;&nbsp;&nbsp;&nbsp;Sinon<br />
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Fermer ce nœud<br />
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Pour tous les nœuds adjacents qui ne sont pas fermé ou n’est pas un obstacle<br />
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Ajouter le nœud à la liste ouverte<br />
			}
			<h3>Explication</h3>
			L’algorithme du A* permet de passer à travers tous les cases en évitant la redondance le plus que possible en fermant des cases. Pour pouvoir se permettre de fermer une case, il faut être sur que le chemin par lequel nous avons passé n’est pas le plus rapide. C’est ici que le concept de coût est utile. Nous passons par les nœuds qui sont potentiellement les plus rapides.<br />
			<img src="AStar.PNG" alt="A*" /><br />
			<a href="bibliographie.html">AI for Game Developpers</a>
			<h3>Calculer le coût</h3>
			Pour calculer le coût d’un nœud, il faut calculer le coût total pour se rendre à ce nœud et ajouter l’heuristique. L’heuristique est tout simplement le coût pour se rendre à la destination au vol d’oiseau. Par exemple, si je suis à la position (4, 5) et que ma destination est (10, 25), l’heuristique sera la distance entre ces deux points. Cette manière permet de trouver les chemins potentiellement plus intéressant le plus rapidement que possible.
			<h2>A* amélioré</h2>
			Notre version du A* améliorer est une manière d’utiliser le même principe que le A* de base dans un monde sans case. Nous plaçons manuellement dans un éditeur des nœuds à des endroits stratégiques. Ensuite, pour savoir quel nœud peut communiquer avec lequel, il faut faire des liens entre ceux-ci. De cette manière, on a une liste de nœuds adjacents, même si nous n’avons pas de case. Avec les nœuds, nous savons très rapidement quelles sont nos possibilités de mouvement.<br /><br />
			<img src="AStarWindows.PNG" alt="A* Windows*" />
			<h3>Se rendre au nœud le plus proche</h3>
			Le principal problème que nous avons rencontré est la manière de se rendre au nœud le plus proche. Au début, l’on doit trouver le nœud le plus proche et se rendre au nœud le plus proche de la fin avant de s’y rendre directement. Par contre, il n’y a aucun moyen de savoir si nous entrons en collision avec des objets. C’est pourquoi nous avons été obligé d’ajouter des boites de collision. De cette manière, on peut trouver le nœud le plus proche sans passer dans un boite de collision.
		</div>
		<br class="clearfloat" />
		<div id="footer"><br /><p align="center">Par Benoît Tremblay et François Roseberry</p></div>
    </div>
	</body>
</html>